package 排序算法.快速排序;

import java.util.Arrays;

/**
 * 快速排序
 * 时间复杂度：O(n * log2n)
 * 空间复杂度：O(1)
 * 不稳定
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr= {8,9,58,5,6,3,5,87,0,5,5};
//        quickSortOneWay(arr,0,arr.length - 1);
//        quickSortTwoWay(arr,0,arr.length - 1);
        quickSortThreeWay(arr,0,arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }

    private static void quickSortThreeWay(int[] arr, int l, int r) {
        if (l >= r){
            return;
        }
        swap(arr,l,(int) Math.random() * (r - l + 1) + l);
        int v = arr[l];
        // arr[l + 1, lt] < v
        int lt = l;
        //arr[gt, r] > v
        int gt = r + 1;
        //arr[lt + 1, i) == v
        int i = lt + 1;
        //结束条件为i = gt
        while (i < gt){
            //如果比v小就交换位置，i++,lt++,最小的值在左边
            if (arr[i] < v){
                swap(arr,i,lt + 1);
                i++;
                lt++;
            //大于的换就和最后一个数字交换，大于的数字的范围扩大，并且i的下标不变，进行下一轮比较
            }else if (arr[i] > v){
                swap(arr, i, gt - 1);
                gt--;
            }else {
                //相等的话i就直接++
                i++;
            }
        }

        //最后比较完一轮后就交换数组中第一个值到该数组的中间，并按切割点进行新一轮的划分与切割
        swap(arr,l,lt);
        quickSortThreeWay(arr,l,lt - 1);
        quickSortThreeWay(arr,gt,r);


    }

    private static void quickSortTwoWay(int[] arr, int l, int r) {
        if (l >= r){
            return;
        }
        //获取中间的分割的值，作为下一次的分割点
        int p = partitionTwoWay(arr,l,r);
        //继续分割左边和右边的数组
        quickSortTwoWay(arr,l,p - 1);
        quickSortTwoWay(arr,p + 1,r);
    }

    private static int partitionTwoWay(int[] arr, int l, int r) {
        //每次随机替换第一个值，来优化每次都拿第一个值来比较
        swap(arr,l,(int) Math.random() * (r - l + 1) + l);
        //每次比较的值为第一个值
        //[l+1, i] < v
        //[j,r] > v
        int v = arr[l];
        //i从第一个值开始
        int i = l + 1;
        //j从最后一个值开始
        int j = r;

        while (true){
            //i比r小，且i下标对应的值比v小的话i就向后面移动
            while (i <= r && arr[i] < v){
                i++;
            }
            //j比l+1大，且j下标对应的值比v大的话j就向前面移动
            while (j >= l + 1 && arr[j] > v){
                j--;
            }
            //当i和j劈叉的时候退出循环
            if (i > j){
                break;
            }
            //当i对应的值比v大或等于，或者j对应值比v小或等于的时候就，交换这两个值，并且下标都移动，之后再进行下一轮的比较
            swap(arr,i,j);
            i++;
            j--;
        }
        //比较完后交换第一个值到最小的位置j,并将该位置返回,作为下一次的切割点
        swap(arr,l,j);
        return j;
    }

    private static void quickSortOneWay(int[] arr, int l, int r) {
        if (l >= r){
            return;
        }
        //获取到中间的固定部分
        int p = partitionOneWay(arr, l , r);

        //继续切割左边和右边的部分，中间值最为切割点
        quickSortOneWay(arr, l, p - 1);
        quickSortOneWay(arr, p + 1, r);
    }

    private static int partitionOneWay(int[] arr, int l, int r) {
        swap(arr,l,(int) Math.random() * (r - l + 1) + l);
        //每次将l的值作为要比较的值，比较固定，使用上面随机数来确定要固定的值来优化比较好，每次调用每次要比较的值都不一样
        int v = arr[l];
        //i默认为l,j默认为i+1,i和j 分别为要查找的中间的值与j(开始的遍历的值和结束遍历的值)
        //[l+1,i] < v
        //[i+1, j) > v
        int i = l;
        int j = i + 1;
        //退出条件为j> r即j越界时就退出
        while (j <= r){
            //每次和v比较如果比v的值要小的或就交换i+1和j位置对应的值，然后i++,j++,如果比v大的或就j++
            if (arr[j] < v){
                swap(arr,i + 1,j);
                i++;
            }
            j++;
        }
        //最后交换第一个值到i的位置(i的位置为左边最小的值的最右边，交换到最小值与最大值区间的中间，即i值左边区间的值都比i对应的值要小，右边都比i对应的值要大)
        swap(arr,l,i);
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
